package com.major.dawn.linkList;

public class LinkedList<T> {

    private LinkNode head;

    private LinkNode tail;

    private int length;

    /**
     * Initialize your data structure here.
     */
    public LinkedList() {
        head = new LinkNode(new Thread());
        tail = new LinkNode(new Thread());
        head.next = tail;
        tail.prev = head;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public Thread get(int index) {
        if (index < 0 || index + 1 > length) {
            return null;
        }
        LinkNode node = getNode(index);
        return node.val;
    }

    private LinkNode getNode(int index) {
        LinkNode current = head.next;
        while (index > 0) {
            current = current.next;
            index--;
        }
        return current;
    }


    /**
     * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(Thread val) {
        addAtIndex(0, val);
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(Thread val) {
        addAtIndex(length,val);
    }

    /**
     * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
     */
    public void addAtIndex(int index, Thread val) {
        if (index < 0 || index > length) {
            return;
        }
        LinkNode linkNode = new LinkNode(val);
        LinkNode cur;

        if (length == index) {
            cur = tail;
        } else {
            cur = getNode(index);
        }
        LinkNode prev = cur.prev;

        linkNode.prev = prev;
        linkNode.next = cur;

        prev.next = linkNode;
        cur.prev = linkNode;

        length++;
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index + 1 > length) {
            return;
        }
        LinkNode cur = getNode(index);
        LinkNode prev = cur.prev;
        LinkNode next = cur.next;
        prev.next = next;
        next.prev = prev;
        cur = null; //for gc
        length--;

    }
}

class LinkNode {

    Thread val;

    LinkNode prev;

    LinkNode next;

    LinkNode(Thread val) {
        this.val = val;
    }

}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

